#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

void PrintArr(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* a,int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int Sort(int* arr,int left,int right)
{
	int key = arr[left];
	int keyi = left;
	while (left<right)
	{
		while (arr[right] >= key && right > left)
		{
			right--;
		}
		while (arr[left] <= key && left < right)
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[keyi], &arr[left]);
	return left;
}

void quickSort(int* arr,int begin,int end)
{
	if (begin >= end)
		return;
	int keyi = Sort(arr, begin, end);
 	quickSort(arr, begin, keyi - 1);
	quickSort(arr, keyi + 1, end);
}


int main()
{
	int arr[11] = { 9,5,6,7,8,9,1,2,3,4 };
	quickSort(arr, 0, sizeof(arr) / sizeof(int)-1);
	PrintArr(arr, sizeof(arr) / sizeof(int));
	return 0;
}